/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root)  return NULL;
        /*
        二叉搜索树的中序遍历序列即为一排序序列；
        观察链表，除了开始及末尾节点，其他节点前驱指向排序前面的一个数，后继指向排序后面的一个数；
        由于需要大幅改动数节点的左右指针，考虑先将其中序遍历序列存入数组中，再重构双向链表。
        */

        vector<Node*> mediumOrder;  //用于存放树的中序遍历序列
        travelTree(root, mediumOrder);

        //重构成双向链表
        int vSize = mediumOrder.size();
        if(vSize == 1){
            //当树中仅有一个节点时，返回树根节点本身
            root->left = root;
            root->right = root;
            return root;
        }
        mediumOrder[0]->left = mediumOrder[vSize - 1];
        mediumOrder[0]->right = mediumOrder[1];
        mediumOrder[vSize - 1]->left = mediumOrder[vSize - 2];
        mediumOrder[vSize - 1]->right = mediumOrder[0];
        for(int i = 1; i < (vSize - 1); ++i){
            mediumOrder[i]->left = mediumOrder[i - 1];
            mediumOrder[i]->right = mediumOrder[i + 1];
        }

        return mediumOrder[0];
    }

    //采用递归遍历二叉搜索树
    void travelTree(Node* pNode, vector<Node*>& mediumOrder){
        if(pNode->left)  travelTree(pNode->left, mediumOrder);
        mediumOrder.push_back(pNode);
        if(pNode->right)  travelTree(pNode->right, mediumOrder);
        return;
    }
};

class Solution {
private:
    Node* head;
public:
    Node* treeToDoublyList(Node* root) {
        if(!root)  return NULL;
        /*
        二叉搜索树的中序遍历序列即为一按顺序排好序的序列；
        ???不太清楚具体递归做法???
        剑指OFFER:每个节点左指针均指向左子树最右边的节点，其右子指针则指向右子树最左边的节点；
        用中序遍历二叉树，当遍历到根节点时，其左右子树已排好序，则将两者与根节点连接则为已排好序的双向链表
        */
        Node* newListEnd = NULL;
        Node** pLastNodeInList = &newListEnd;
        travelTree(root, pLastNodeInList);

        //处理新表头表尾
        head->left = *pLastNodeInList;
        (*pLastNodeInList)->right = head;

        return head;
    }

    /*
    算法流程：(pre为上个链表排序的末尾)按照中序遍历顺序cur->left = pre,pre.right = cur,pre = pNode；
    函数参数使用了二级指针,作用类似于指针引用，需要修改指针的地址
    */
    void travelTree(Node* pNode, Node** pLastNodeInList){
        if(pNode->left)  travelTree(pNode->left, pLastNodeInList);

        if(!(*pLastNodeInList))  head = pNode;  //当前到达最左边节点

        pNode->left = *pLastNodeInList;
        if((*pLastNodeInList)) (*pLastNodeInList)->right = pNode;
        (*pLastNodeInList) = pNode;

        if(pNode->right)  travelTree(pNode->right, pLastNodeInList);
    }
};